/*-------------------------------------------------------------------------
 *
 * gist.h
 *	  GiST 索引的公共 API。此 API 公开给实现 GiST 索引的
 *	  个人，因此向后不兼容的更改应谨慎进行。
 *
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 * src/include/access/gist.h
 *
 *-------------------------------------------------------------------------
 */
#ifndef GIST_H
#define GIST_H

#include "access/itup.h"
#include "access/transam.h"
#include "access/xlog.h"
#include "access/xlogdefs.h"
#include "storage/block.h"
#include "storage/bufpage.h"
#include "utils/relcache.h"

/*
 * GiST 索引的 amproc 索引。
 */
#define GIST_CONSISTENT_PROC			1
#define GIST_UNION_PROC					2
#define GIST_COMPRESS_PROC				3
#define GIST_DECOMPRESS_PROC			4
#define GIST_PENALTY_PROC				5
#define GIST_PICKSPLIT_PROC				6
#define GIST_EQUAL_PROC					7
#define GIST_DISTANCE_PROC				8
#define GIST_FETCH_PROC					9
#define GIST_OPTIONS_PROC				10
#define GIST_SORTSUPPORT_PROC			11
#define GISTNProcs					11

/*
 * GiST 索引页面中的页面不透明数据。
 */
#define F_LEAF				(1 << 0)	/* 叶页面 */
#define F_DELETED			(1 << 1)	/* 页面已经被删除 */
#define F_TUPLES_DELETED	(1 << 2)	/* 页面上的某些元组已被
										 * 删除 */
#define F_FOLLOW_RIGHT		(1 << 3)	/* 右侧页面没有下行链接 */
#define F_HAS_GARBAGE		(1 << 4)	/* 页面上的某些元组是死的，
										 * 但尚未删除 */

/*
 * NSN（节点序列号）是一个特殊用途的 LSN，它存储在每个索引页面的 GISTPageOpaqueData 中，并且仅在页面分裂期间更新。通过在 GISTSearchItem.parentlsn 中记录父级的 LSN，可以通过检查 parentlsn < child's NSN 检测并发子页面分裂，并妥善处理。子页面的 LSN 对此目的来说是不够的，因为它在每次页面更改时都会更新。
 */
typedef XLogRecPtr GistNSN;

/*
 * 在索引构建期间使用的伪 LSN / NSN 值。必须小于索引构建完成后生成的任何真实或伪（未记录）LSN，以便所有分裂都被视为完成。
 */
#define GistBuildLSN	((XLogRecPtr) 1)

/*
 * 为与预 9.3 服务器的磁盘兼容性，NSN 作为两个 32 位字段存储在磁盘上，与 LSN 相同。
 */
typedef PageXLogRecPtr PageGistNSN;

typedef struct GISTPageOpaqueData
{
	PageGistNSN nsn;			/* 此值必须在页面分裂时更改 */
	BlockNumber rightlink;		/* 如果有下一个页面 */
	uint16		flags;			/* 参见上述位定义 */
	uint16		gist_page_id;	/* 用于识别 GiST 索引 */
} GISTPageOpaqueData;

typedef GISTPageOpaqueData *GISTPageOpaque;

/*
 * GiST 索引元组和索引键的最大可能大小。计算基于 GiST 页面应至少能容纳 4 个元组的假设。在理论上，当页面可以容纳 3 个元组时，GiST 索引可以是功能性的。但这似乎相当低效，因此我们使用一个稍微保守的估计。
 *
 * 对于单列索引，索引键的最大大小是真实的。因此，此估计应被用来确定 GiST 索引键的最大大小是否有意义。对于多列索引，用户可能能够使用操作类参数调整键大小。
 */
#define GISTMaxIndexTupleSize	\
	MAXALIGN_DOWN((BLCKSZ - SizeOfPageHeaderData - sizeof(GISTPageOpaqueData)) / \
				  4 - sizeof(ItemIdData))

#define GISTMaxIndexKeySize	\
	(GISTMaxIndexTupleSize - MAXALIGN(sizeof(IndexTupleData)))

/*
 * 页面 ID 是出于 pg_filedump 和类似工具的便利性，否则它们很难区分不同类型的索引页面。它应该是页面上的最后两个字节。由于对齐考虑，这在某种程度上是“免费”的。
 */
#define GIST_PAGE_ID		0xFF81


/*
 * 这是由 PickSplit 方法返回的拆分向量。
 * PickSplit 应该将要进入左侧的元组索引填充到
 * spl_left[] 中，而要进入右侧的则填充到 spl_right[] 中（注意该方法
 * 负责为这两个数组分配内存！）。元组的计数
 * 放入 spl_nleft/spl_nright，且 spl_ldatum/spl_rdatum 必须设置为
 * 每侧的联合键。
 *
 * 如果 spl_ldatum_exists 和 spl_rdatum_exists 为真，则我们正在使用
 * 非首个索引列执行“二次拆分”。在这种情况下，关于页面拆分的一些
 * 决定已经做出，被传递给 PickSplit 的元组集仅是那些我们尚未决定的元组。
 * spl_ldatum/spl_rdatum 然后包含已选择进入左侧或右侧的元组的联合键。
 * 理想情况下，PickSplit 方法应该在决定如何处理剩余元组时考虑这些
 * 键，即它应该尝试从这些联合中“扩展”，以最小方式扩展。
 * 如果它这样做，它应将给定元组的键联合到现有的 spl_ldatum/spl_rdatum
 * 值中，而不是从头开始设置这些值，然后将 spl_ldatum_exists/spl_rdatum_exists
 * 设置为 false 以表明它已完成此操作。
 *
 * 如果 PickSplit 方法未能清除 spl_ldatum_exists/spl_rdatum_exists，
 * 核心 GiST 代码将自行决定如何将二次拆分结果与之前选择的元组合并，
 * 然后从头计算联合键。这是一种可行但通常不是最佳的方法。
 */
typedef struct GIST_SPLITVEC
{
	OffsetNumber *spl_left;		/* 左侧的条目数组 */
	int			spl_nleft;		/* 此数组的大小 */
	Datum		spl_ldatum;		/* spl_left 中的键的联合 */
	bool		spl_ldatum_exists;	/* true, 如果 spl_ldatum 已经存在。 */

	OffsetNumber *spl_right;	/* 右侧的条目数组 */
	int			spl_nright;		/* 数组的大小 */
	Datum		spl_rdatum;		/* spl_right 中的键的联合 */
	bool		spl_rdatum_exists;	/* true, 如果 spl_rdatum 已经存在。 */
} GIST_SPLITVEC;

/*
 * GiST 节点上的一个条目。包含键，以及其自身的位置
 * (rel,page,offset)，可以提供匹配的指针。
 * leafkey 是一个标志，用来告诉我们条目是否位于叶子节点中。
 */
typedef struct GISTENTRY
{
	Datum		key;
	Relation	rel;
	Page		page;
	OffsetNumber offset;
	bool		leafkey;
} GISTENTRY;

#define GistPageGetOpaque(page) ( (GISTPageOpaque) PageGetSpecialPointer(page) )

#define GistPageIsLeaf(page)	( GistPageGetOpaque(page)->flags & F_LEAF)
#define GIST_LEAF(entry) (GistPageIsLeaf((entry)->page))

#define GistPageIsDeleted(page) ( GistPageGetOpaque(page)->flags & F_DELETED)

#define GistTuplesDeleted(page) ( GistPageGetOpaque(page)->flags & F_TUPLES_DELETED)
#define GistMarkTuplesDeleted(page) ( GistPageGetOpaque(page)->flags |= F_TUPLES_DELETED)
#define GistClearTuplesDeleted(page)	( GistPageGetOpaque(page)->flags &= ~F_TUPLES_DELETED)

#define GistPageHasGarbage(page) ( GistPageGetOpaque(page)->flags & F_HAS_GARBAGE)
#define GistMarkPageHasGarbage(page) ( GistPageGetOpaque(page)->flags |= F_HAS_GARBAGE)
#define GistClearPageHasGarbage(page)	( GistPageGetOpaque(page)->flags &= ~F_HAS_GARBAGE)

#define GistFollowRight(page) ( GistPageGetOpaque(page)->flags & F_FOLLOW_RIGHT)
#define GistMarkFollowRight(page) ( GistPageGetOpaque(page)->flags |= F_FOLLOW_RIGHT)
#define GistClearFollowRight(page)	( GistPageGetOpaque(page)->flags &= ~F_FOLLOW_RIGHT)

#define GistPageGetNSN(page) ( PageXLogRecPtrGet(GistPageGetOpaque(page)->nsn))
#define GistPageSetNSN(page, val) ( PageXLogRecPtrSet(GistPageGetOpaque(page)->nsn, val))


/*
 * 在删除的页面上，我们存储这个结构体。被删除的页面不包含任何
 * 元组，因此我们不使用带有行指针的正常页面布局。相反，
 * 这个结构体紧随标准页面头部存储。pd_lower 指向
 * 这个结构体的结束。如果我们在将来向这个结构体添加字段，
 * 我们可以通过 pd_lower 区分旧格式和新格式。
 */
typedef struct GISTDeletedPageContents
{
	/* 可以在扫描中查看页面的最后 xid */
	FullTransactionId deleteXid;
} GISTDeletedPageContents;

static inline void
GistPageSetDeleted(Page page, FullTransactionId deletexid)
{
	Assert(PageIsEmpty(page));

	GistPageGetOpaque(page)->flags |= F_DELETED;
	((PageHeader) page)->pd_lower = MAXALIGN(SizeOfPageHeaderData) + sizeof(GISTDeletedPageContents);

	((GISTDeletedPageContents *) PageGetContents(page))->deleteXid = deletexid;
}

static inline FullTransactionId
GistPageGetDeleteXid(Page page)
{
	Assert(GistPageIsDeleted(page));

	/* deleteXid 字段是否存在？ */
	if (((PageHeader) page)->pd_lower >= MAXALIGN(SizeOfPageHeaderData) +
		offsetof(GISTDeletedPageContents, deleteXid) + sizeof(FullTransactionId))
	{
		return ((GISTDeletedPageContents *) PageGetContents(page))->deleteXid;
	}
	else
		return FullTransactionIdFromEpochAndXid(0, FirstNormalTransactionId);
}

/*
 * GISTENTRY 结构体的向量；用户定义的方法 union 和 picksplit
 * 将其作为参数之一
 */
typedef struct
{
	int32		n;				/* 元素数量 */
	GISTENTRY	vector[FLEXIBLE_ARRAY_MEMBER];
} GistEntryVector;

#define GEVHDRSZ	(offsetof(GistEntryVector, vector))

/*
 * 初始化 GISTENTRY 的宏
 */
#define gistentryinit(e, k, r, pg, o, l) \
	do { (e).key = (k); (e).rel = (r); (e).page = (pg); \
		 (e).offset = (o); (e).leafkey = (l); } while (0)

#endif							/* GIST_H */
